{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Binary Search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个&nbsp;<code>n</code>&nbsp;个元素有序的（升序）整型数组&nbsp;<code>nums</code> 和一个目标值&nbsp;<code>target</code> &nbsp;，写一个函数搜索&nbsp;<code>nums</code>&nbsp;中的 <code>target</code>，如果目标值存在返回下标，否则返回 <code>-1</code>。</p>\n",
    "\n",
    "<p><br>\n",
    "<strong>示例 1:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> <code>nums</code> = [-1,0,3,5,9,12], <code>target</code> = 9\n",
    "<strong>输出:</strong> 4\n",
    "<strong>解释:</strong> 9 出现在 <code>nums</code> 中并且下标为 4\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> <code>nums</code> = [-1,0,3,5,9,12], <code>target</code> = 2\n",
    "<strong>输出:</strong> -1\n",
    "<strong>解释:</strong> 2 不存在 <code>nums</code> 中因此返回 -1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li>你可以假设 <code>nums</code>&nbsp;中的所有元素是不重复的。</li>\n",
    "\t<li><code>n</code>&nbsp;将在&nbsp;<code>[1, 10000]</code>之间。</li>\n",
    "\t<li><code>nums</code>&nbsp;的每个元素都将在&nbsp;<code>[-9999, 9999]</code>之间。</li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [binary-search](https://leetcode.cn/problems/binary-search/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [binary-search](https://leetcode.cn/problems/binary-search/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[-1,0,3,5,9,12]\\n9', '[-1,0,3,5,9,12]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        sorted_list = [(b, a) for a, b in zip(scores, ages)]\n",
    "        sorted_list.sort(key=lambda x:(x[0], x[1]))\n",
    "        def binary_search(arr, target):\n",
    "            l, r = 0, len(arr) - 1\n",
    "            while l <= r:\n",
    "                mid = (l+r) // 2\n",
    "                if arr[mid] < target:\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            return l\n",
    "        \n",
    "        # d = [sorted_list[1]]\n",
    "        ans = sorted_list[0][1]\n",
    "        n = len(sorted_list)\n",
    "        f = [[0,0] for _ in range(n)]\n",
    "        # print(f)\n",
    "        # print(sorted_list)\n",
    "        for i in range(n):\n",
    "            f[i][0] = 1\n",
    "            f[i][1] = sorted_list[i][1]\n",
    "            for j in range(i):\n",
    "                if sorted_list[i][1] >= sorted_list[j][1]:\n",
    "                    if f[i][0] <= f[j][0] + 1:\n",
    "                        f[i][0] = f[j][0] + 1\n",
    "                        f[i][1] = max(f[j][1] + sorted_list[i][1], f[i][1])\n",
    "            ans = max(ans, f[i][1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# name:Aoobex\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        people = sorted(zip(scores,ages))\n",
    "        n = len(scores)\n",
    "        @cache\n",
    "        def back_search(i):\n",
    "            score = people[i][0]\n",
    "            ans = 0\n",
    "            for j in range(i):\n",
    "                if people[j][1] <= people[i][1]:\n",
    "                    ans = max(ans,back_search(j))\n",
    "                else:\n",
    "                    if people[j][0] >= people[i][0]:\n",
    "                        ans = max(ans,back_search(j))\n",
    "            return ans+score\n",
    "\n",
    "        return max(back_search(i) for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# name:Aoobex\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        people = sorted(zip(scores,ages))\n",
    "        n = len(scores)\n",
    "        @cache\n",
    "        def back_search(i):\n",
    "            score = people[i][0]\n",
    "            ans = 0\n",
    "            for j in range(i):\n",
    "                if people[j][1] <= people[i][1]:\n",
    "                    ans = max(ans,back_search(j))\n",
    "                else:\n",
    "                    if people[j][0] >= people[i][0]:\n",
    "                        ans = max(ans,back_search(j))\n",
    "            return ans+score\n",
    "\n",
    "        return max(back_search(i) for i in range(n-1,-1,-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    d0=[]\n",
    "    d1=[]\n",
    "\n",
    "    def search(self,currentn:int,prices:[],fee:int):\n",
    "        #这里处理第 currentn 天开始的情况， 结果将填写 d0[currentn]和 d1[currentn]\n",
    "        if currentn >0:\n",
    "            self.search(currentn-1,prices,fee)\n",
    "            self.d0[currentn] = max(self.d0[currentn-1],self.d1[currentn-1]+prices[currentn-1]-fee)\n",
    "            self.d1[currentn] = max(self.d1[currentn-1],self.d0[currentn-1]-prices[currentn-1])\n",
    "            return\n",
    "        self.d0[0] = 0\n",
    "        self.d1[0] = -sys.maxsize - 1\n",
    "\n",
    "    def maxProfit(self, prices: List[int], fee: int) -> int:\n",
    "        self.d0 = [0 for i in range(len(prices)+1)]\n",
    "        self.d1 = [0 for i in range(len(prices)+1)]\n",
    "        self.search(len(prices),prices,fee)\n",
    "        return self.d0[len(prices)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validNumber(self, s: str) -> bool:\n",
    "        s = s.strip()\n",
    "        return re.search(r\"^[\\+-]?\\d+\\.?\\d*([eE][\\+-]?\\d+)?$|^[+-]?\\.\\d+([eE][\\+-]?\\d+)?$\", s) is not None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:            \n",
    "    def validNumber(self, s: str) -> bool:\n",
    "        s = s.strip()\n",
    "        return re.search(r\"^[\\+-]?\\d+\\.?\\d*([eE][\\+-]?\\d+)?$|^[+-]?\\.\\d+([eE][\\+-]?\\d+)?$\", s) is not None\n",
    "        # try:\n",
    "        #     a = s.lower().strip()\n",
    "        #     if a.startswith('0'):\n",
    "        #         a = '1'+a.lstrip('0')\n",
    "        #     if a.startswith('-0'):\n",
    "        #         a = '1'+a.lstrip('-0')\n",
    "        #     print(a)\n",
    "        #     if a.endswith('e') or a.endswith('e.'):\n",
    "        #         return False\n",
    "        #     a = a.replace('e','*1')\n",
    "        #     # print(a)\n",
    "        #     a = float(eval(a))\n",
    "        #     return True\n",
    "        # except Exception as e:\n",
    "        #     return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "\n",
    "class Solution:\n",
    "    def validNumber(self, s: str) -> bool:\n",
    "        return re.search(r'^\\s*[+-]?(\\d+|(\\d*\\.\\d+)|(\\d+\\.\\d*))([eE][+-]?\\d+)?\\s*$', s) is not None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "\n",
    "class Solution:\n",
    "    def validNumber(self, s: str) -> bool:\n",
    "        if re.search(\"^[-|+]?(\\d+\\.?(\\d+)?|(\\d+)?\\.\\d+)([e|E][-|+]?\\d+)?$\", s.strip()):\n",
    "            return True\n",
    "        else:\n",
    "            return False  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class BSTIterator:\n",
    "\n",
    "    def __init__(self, root: TreeNode):\n",
    "        \n",
    "        # Array containing all the nodes in the sorted order\n",
    "        self.nodes_sorted = []\n",
    "        \n",
    "        # Pointer to the next smallest element in the BST\n",
    "        self.index = -1\n",
    "        \n",
    "        # Call to flatten the input binary search tree\n",
    "        self._inorder(root)\n",
    "        \n",
    "    def _inorder(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        self._inorder(root.left)\n",
    "        self.nodes_sorted.append(root.val)\n",
    "        self._inorder(root.right)\n",
    "\n",
    "    def next(self) -> int:\n",
    "        \"\"\"\n",
    "        @return the next smallest number\n",
    "        \"\"\"\n",
    "        self.index += 1\n",
    "        return self.nodes_sorted[self.index]\n",
    "\n",
    "    def hasNext(self) -> bool:\n",
    "        \"\"\"\n",
    "        @return whether we have a next smallest number\n",
    "        \"\"\"\n",
    "        return self.index + 1 < len(self.nodes_sorted)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class BSTIterator:\n",
    "\n",
    "    def __init__(self, root: Optional[TreeNode]):\n",
    "        self.queue = collections.deque()\n",
    "        self.inorder(root)\n",
    "    \n",
    "    def inorder(self, node):\n",
    "        if not node:\n",
    "            return None\n",
    "        self.inorder(node.left)\n",
    "        self.queue.append(node.val)\n",
    "        self.inorder(node.right)\n",
    "\n",
    "    def next(self) -> int:\n",
    "        return self.queue.popleft()\n",
    "\n",
    "    def hasNext(self) -> bool:\n",
    "        return len(self.queue) > 0\n",
    "\n",
    "\n",
    "# Your BSTIterator object will be instantiated and called as such:\n",
    "# obj = BSTIterator(root)\n",
    "# param_1 = obj.next()\n",
    "# param_2 = obj.hasNext()\n",
    "\n",
    "\n",
    "\n",
    "# https://leetcode.cn/problems/binary-search-tree-iterator/solutions/684560/fu-xue-ming-zhu-dan-diao-zhan-die-dai-la-dkrm/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode.com/contest/weekly-contest-135/problems/binary-search-tree-to-greater-sum-tree/\n",
    "import os, sys, shutil, glob, re\n",
    "import time, calendar\n",
    "from datetime import datetime, timezone\n",
    "import hashlib, zipfile, zlib\n",
    "from math import *\n",
    "from operator import itemgetter\n",
    "from functools import wraps, cmp_to_key, reduce\n",
    "from itertools import count, combinations, permutations\n",
    "from collections import namedtuple, defaultdict, Counter\n",
    "from queue import Queue\n",
    "from bisect import bisect_left, bisect_right\n",
    "\n",
    "def refreshGlobals():\n",
    "  pass\n",
    "\n",
    "refreshGlobals()\n",
    "\n",
    "\n",
    "def getTreeNodeSum(node):\n",
    "  if not node:\n",
    "    return 0\n",
    "  return node.val + getTreeNodeSum(node.left) + getTreeNodeSum(node.right)\n",
    "\n",
    "def isLeaf(node):\n",
    "  return (not node.left) and (not node.right)\n",
    "\n",
    "\n",
    "# 递归修改树上节点 node.val → greaterSum\n",
    "def dfs(node, type, parNode):\n",
    "  if not node:\n",
    "    return\n",
    "\n",
    "  node.originalVal = node.val\n",
    "\n",
    "  if type == 'right':\n",
    "    node.val = parNode.val - parNode.originalVal - getTreeNodeSum(node.left)\n",
    "  else:\n",
    "    node.val = node.val + getTreeNodeSum(node.right) + parNode.val\n",
    "\n",
    "  dfs(node.left, 'left', node)\n",
    "  dfs(node.right, 'right', node)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "  def bstToGst(self, root):  # -> TreeNode\n",
    "    dfs(root, 'left', TreeNode(0))\n",
    "    return root\n",
    "\n",
    "if __name__ == '__main__' and ('SJDEAK' in os.environ):\n",
    "  from utils.tree import TreeNode, array2TreeNode\n",
    "\n",
    "  def test(*args):\n",
    "    print('输入数据: ', *args)\n",
    "    print('结果: ', Solution().bstToGst(*args), end='\\n-----\\n')\n",
    "\n",
    "\n",
    "  test()\n",
    "  test()\n",
    "else:\n",
    "  print = lambda *args, **kwargs: None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self, nums: List[int], target: int) -> int:\n",
    "        left, right = 0, len(nums) - 1\n",
    "        while left <= right:\n",
    "            pivot = left + (right - left) // 2\n",
    "            if nums[pivot] == target:\n",
    "                return pivot\n",
    "            if target < nums[pivot]:\n",
    "                right = pivot - 1\n",
    "            else:\n",
    "                left = pivot + 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self, nums: 'List[int]', target: 'int') -> 'int':\n",
    "        length = len(nums)\n",
    "        a = 0\n",
    "        b = (length-1)\n",
    "        if nums[0]==target:\n",
    "            return 0\n",
    "        if nums[b]==target:\n",
    "            return b\n",
    "        while True:\n",
    "            if nums[(a+b)//2]>target:\n",
    "                b = (a+b)//2 \n",
    "            if nums[(a+b)//2]<target:\n",
    "                a = (a+b)//2\n",
    "            if nums[(a+b)//2] == target:\n",
    "                return ((a+b)//2)\n",
    "                break\n",
    "            if ((a+b)//2) == a:\n",
    "                return(-1)\n",
    "                break\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not nums:\n",
    "            return -1\n",
    "        i, j = 0, len(nums) - 1\n",
    "        while i <= j:\n",
    "            m = (i + j) // 2\n",
    "            if nums[m] > target:\n",
    "                j = m - 1\n",
    "            elif nums[m] < target:\n",
    "                i = m + 1\n",
    "            else:\n",
    "                return m\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self, nums: 'List[int]', target: 'int') -> 'int':\n",
    "        right = len(nums)-1\n",
    "        left = 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            print(left,mid,right)\n",
    "            if nums[mid] > target:\n",
    "                right = mid-1\n",
    "            elif nums[mid] < target:\n",
    "                left = mid +1\n",
    "            else:\n",
    "                return mid\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        start, end = 0, len(nums)-1\n",
    "        while start <= end:\n",
    "            mid = (start+end)//2\n",
    "            if nums[mid] == target:\n",
    "                return mid\n",
    "            elif nums[mid] < target:\n",
    "                start = mid + 1\n",
    "            else:\n",
    "                end = mid - 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self, nums: 'List[int]', target: 'int') -> 'int':\n",
    "        left, right = 0, len(nums)-1\n",
    "        while left <= right:\n",
    "            mid = left + ((right-left)>>1)\n",
    "            if target == nums[mid]:\n",
    "                return mid\n",
    "            elif nums[mid] < target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(nums) == 0:\n",
    "            return -1\n",
    "        \n",
    "        \n",
    "        l,r=0,len(nums)-1\n",
    "        if target < nums[l] or target > nums[r]:\n",
    "            return -1\n",
    "        \n",
    "        \n",
    "        m = 0\n",
    "        L = -1\n",
    "        R = -1\n",
    "        while l != r:\n",
    "            m = int((l+r)/2)\n",
    "            print(21,l,r,m)\n",
    "            if target == nums[m]:\n",
    "                return m\n",
    "            elif target < nums[m]:\n",
    "                r = m\n",
    "            else:\n",
    "                l = m\n",
    "                \n",
    "            print(30,l,r,m)\n",
    "            if R==r and l==L:\n",
    "                if nums[r] == target:\n",
    "                    return r\n",
    "                return -1\n",
    "            R = r\n",
    "            L = l\n",
    "            print(35,l,r,m)\n",
    "\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\r\n",
    "# @lc app=leetcode.cn id=704 lang=python3\r\n",
    "#\r\n",
    "# [704] 二分查找\r\n",
    "#\r\n",
    "class Solution:\r\n",
    "    def search(self, nums: List[int], target: int) -> int:\r\n",
    "        \r\n",
    "        # if len(nums) % 2:\r\n",
    "        #     index_i = int(len(nums) / 2)\r\n",
    "        #     index_j = int(len(nums) / 2)\r\n",
    "        # else:\r\n",
    "        #     index_i = int(len(nums) / 2) - 1\r\n",
    "        #     index_j = int(len(nums) / 2)\r\n",
    "        \r\n",
    "        # while index_i > -1 and index_j < len(nums) :\r\n",
    "        #     if nums[index_i] == target:\r\n",
    "        #         return index_i\r\n",
    "            \r\n",
    "        #     if nums[index_j] == target:\r\n",
    "        #         return index_j\r\n",
    "            \r\n",
    "        #     index_i = index_i - 1\r\n",
    "        #     index_j = index_j + 1\r\n",
    "        \r\n",
    "        # return -1\r\n",
    "\r\n",
    "        temp = 0\r\n",
    "\r\n",
    "        while len(nums):\r\n",
    "\r\n",
    "            if len(nums) % 2:\r\n",
    "                index_i = int(len(nums) / 2)\r\n",
    "                index_j = int(len(nums) / 2)\r\n",
    "            else:\r\n",
    "                index_i = int(len(nums) / 2) - 1\r\n",
    "                index_j = int(len(nums) / 2)\r\n",
    "            \r\n",
    "            if nums[index_i] == target:\r\n",
    "                return index_i + temp\r\n",
    "            \r\n",
    "            if nums[index_j] == target:\r\n",
    "                return index_j + temp\r\n",
    "            \r\n",
    "            if target > nums[index_j]:\r\n",
    "                temp += index_j + 1\r\n",
    "                nums[:] = nums[index_j+1:]\r\n",
    "                continue\r\n",
    "            \r\n",
    "            if target < nums[index_i]:\r\n",
    "                nums[:] = nums[:index_i]\r\n",
    "                continue\r\n",
    "        \r\n",
    "        return -1\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self, nums: 'List[int]', target: 'int') -> 'int':\n",
    "        \n",
    "        high = len(nums)-1     \n",
    "        low  = 0\n",
    "\n",
    "        while high >= low :          # 设定区间\n",
    "\n",
    "            mid =  (high+low)//2\n",
    "\n",
    "            if nums[mid] == target:\n",
    "                return mid\n",
    "\n",
    "            elif nums[mid] < target:\n",
    "                low = mid + 1\n",
    "\n",
    "            else:\n",
    "                high = mid - 1\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self, nums: List[int], target: int) -> int:\n",
    "        l, r = 0, len(nums) - 1\n",
    "        \n",
    "        while l <= r:\n",
    "            m = (l + r) // 2\n",
    "            if nums[m] == target:\n",
    "                return m\n",
    "            elif nums[m] > target:\n",
    "                r = m - 1\n",
    "            elif nums[m] < target:\n",
    "                l = m + 1\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self, nums: List[int], target: int) -> int:\n",
    "        if nums:\n",
    "            left = mid = 0\n",
    "            right = len(nums)\n",
    "            while left < right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if nums[mid] == target:\n",
    "                    return mid\n",
    "                elif nums[mid] < target:\n",
    "                    left = mid + 1\n",
    "                elif nums[mid] > target:\n",
    "                    right = mid\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def search(self, nums: List[int], target: int) -> int:\r\n",
    "        if not nums: return -1\r\n",
    "        l,r = 0, len(nums)-1\r\n",
    "        while l<=r:\r\n",
    "            mid = (l+r)//2\r\n",
    "            if nums[mid] == target:\r\n",
    "                return mid\r\n",
    "            elif nums[mid] < target:\r\n",
    "                l = mid + 1\r\n",
    "            else:\r\n",
    "                r = mid - 1\r\n",
    "        return -1\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# import bisect\n",
    "class Solution:\n",
    "    def search(self, nums: List[int], target: int) -> int:\n",
    "        try:\n",
    "            return nums.index(target)\n",
    "        except:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self, nums: List[int], target: int) -> int:\n",
    "        i = 0\n",
    "        j = len(nums)-1\n",
    "        while i <j:\n",
    "            p = int((i+j)/2)\n",
    "            if nums[p] ==target:\n",
    "                return p\n",
    "            elif nums[p]>target:\n",
    "                j = p-1\n",
    "            else:\n",
    "                i = p+1\n",
    "        if nums[i]==target:\n",
    "            return i\n",
    "        else: return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self, nums: List[int], target: int) -> int:\n",
    "        if target not in nums:\n",
    "            return -1\n",
    "        else:\n",
    "            for i in range(len(nums)):\n",
    "                if nums[i] == target:\n",
    "                    return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self, nums: List[int], target: int) -> int:\n",
    "        '''\n",
    "        low, high = 0, len(nums)\n",
    "        mid = (low + high) // 2\n",
    "        while low < high:\n",
    "            mid = (low + high) // 2\n",
    "            if nums[mid] < target:\n",
    "                low = mid + 1\n",
    "            elif nums[mid] > target:\n",
    "                high = mid\n",
    "            else:\n",
    "                return mid\n",
    "        return -1\n",
    "        '''\n",
    "        try:\n",
    "            return nums.index(target)\n",
    "        except:\n",
    "            return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self, nums: List[int], target: int) -> int:\n",
    "        # if len(nums) == 0:\n",
    "        #     return -1\n",
    "        # else:\n",
    "        #     mid = len(nums) // 2\n",
    "        #     if nums[mid] == target:\n",
    "        #         return mid\n",
    "        #     else:\n",
    "        #         if target < nums[mid]:\n",
    "        #             return search(nums[:mid],target)\n",
    "        #         else:\n",
    "        #             return search(nums[mid+1:len(nums)],target)\n",
    "        \n",
    "        left = 0\n",
    "        right = len(nums) - 1\n",
    "        while(left <= right):\n",
    "            mid = (left+right) // 2\n",
    "            if target < nums[mid]:\n",
    "                right = mid -1\n",
    "            elif target > nums[mid] :\n",
    "                left = mid +1\n",
    "            else:\n",
    "                return mid\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def search(self, nums: List[int], target: int) -> int:\n",
    "        if not nums: return -1\n",
    "        medic = Counter(nums)\n",
    "        if target not in medic: return -1\n",
    "        l, r = 0, len(nums)\n",
    "        while l <= r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if target == nums[mid]:\n",
    "                return mid\n",
    "            if target < nums[mid]:\n",
    "                r = mid -1\n",
    "            else:\n",
    "                l = mid +1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self, nums: List[int], target: int) -> int:\n",
    "        return self.bsearch(nums, 0, len(nums), target)\n",
    "\n",
    "    def bsearch(self, nums, s, e, target):\n",
    "        if e < s:\n",
    "            return -1\n",
    "        if s == (e-1):\n",
    "            if nums[s] == target:\n",
    "                return s\n",
    "            else:\n",
    "                return -1\n",
    "\n",
    "        m = (s+e) // 2\n",
    "\n",
    "        if nums[m] <= target:\n",
    "            return self.bsearch(nums, m, e, target)\n",
    "        else:\n",
    "            return self.bsearch(nums, s, m, target)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        l,r = 0,n\n",
    "        while l<r:\n",
    "            mid = (l+r)//2\n",
    "            if nums[mid]==target:\n",
    "                return mid \n",
    "            elif nums[mid]<target:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self, nums: List[int], target: int) -> int:\n",
    "        if target in  nums:\n",
    "            result =  nums.index(target)\n",
    "            return result\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self,nums:List[int],target:int)->int:\n",
    "        left=0\n",
    "        right=len(nums)-1\n",
    "        while left<=right:\n",
    "            mid=(right-left)//2+left\n",
    "            if nums[mid]>target:\n",
    "                right=mid-1\n",
    "            elif nums[mid]<target:\n",
    "                left=mid+1\n",
    "            else:\n",
    "                return mid\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self, nums: List[int], target: int) -> int:\n",
    "        left, right = 0, len(nums) - 1\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if nums[mid] == target:\n",
    "                return mid\n",
    "            elif nums[mid] > target:\n",
    "                right = mid - 1\n",
    "            elif nums[mid] < target:\n",
    "                left = mid + 1\n",
    "\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self, nums: List[int], target: int) -> int:\n",
    "        left, right = 0, len(nums) \n",
    "        while left < right:\n",
    "            tmp = (right - left) // 2 + left\n",
    "            print(nums, left, right, tmp)\n",
    "            if nums[tmp] < target:\n",
    "                left = tmp + 1\n",
    "            elif nums[tmp] > target:\n",
    "                right = tmp \n",
    "            else:\n",
    "                return tmp\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self, nums: List[int], target: int) -> int:\n",
    "        left = 0\n",
    "        right = len(nums)-1\n",
    "        while(left<=right):\n",
    "            t = (right+left)//2\n",
    "            if(target>nums[t]):\n",
    "                left = t+1\n",
    "            elif(target<nums[t]):\n",
    "                right = t-1\n",
    "            else:\n",
    "                return t\n",
    "            \n",
    "            # if(left>right):\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self, nums: List[int], target: int) -> int:\n",
    "        left = 0\n",
    "        right = len(nums)-1\n",
    "        while right>=left:\n",
    "            mid = left+(right-left)//2\n",
    "            if nums[mid]>target:\n",
    "                right = mid - 1\n",
    "            elif nums[mid]<target:\n",
    "                left = mid + 1\n",
    "            else: return mid\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self, nums: List[int], target: int) -> int:\n",
    "        # []\n",
    "        left = 0\n",
    "        right = len(nums) - 1\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if nums[mid] < target: left = mid + 1\n",
    "            elif nums[mid] > target: right = mid - 1\n",
    "            else: return mid\n",
    "        return -1\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
